For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

2
votes
2answers
30 views

$X$ be a non-empty subset of irrational numbers such that sum of any two elements of $X$ is rational ; then is there any upper bound for $|X|$?

Let $X$ be a non-empty subset of irrational numbers such that sum of any two elements of $X$ is rational ; then is there any possible upper bound for the cardinality of $X$ ? Can $X$ be infinite ?( I ...
0
votes
0answers
16 views

Different ways to leave linearly dependent vectors of a set of vectors

Let a set $S=\left\{ {{\mathbf{v}}_{i}}:i\in \mathbb{Z}_{n}^{+} \right\}$, where $\mathbb{Z}_{n}^{+}=\left\{ 1,2,...,n \right\}$ and ${{\mathbf{v}}_{i}}\in {{\mathbb{R}}^{m}}$ for each $i\in ...
0
votes
0answers
50 views

Formula for combinations-

While I was thinking I found this formula: $\binom{n-k}{r-k} + \binom{n-k}{r-k +1} + \binom{n-k}{r-k +2} + ....+ \binom{n-k}{r-k +r}$ Where ...
6
votes
2answers
66 views

number of integer solutions to $2x_1 + x_2 + x_3 = n$

I'm working on a problem for which I need to efficiently compute the number of integer solutions to equations of the form $x_1 + \cdots + x_k = n$ with some subset of $\{x_1, \dots, x_n\}$ equivalent. ...
1
vote
2answers
33 views

Confused about when to use permutations or combinations

How many baseball teams can be formed from 15 players if 3 only pitch and the others play any of the remaining 8 positions? I'm thinking that this is permutations, but my teacher says it is ...
2
votes
1answer
45 views

Stars and Bars with an odd constraint.

Stars and bars is a classic combinatorics question, but I've run into a variant I've never seen before. I have $n$ stars. Rather than group them into piles using $k - 1$ bars, I want to group them ...
3
votes
1answer
108 views

Why is a Pair of Tens better than a Pair of Aces in Texas Hold 'Em?

A couple years ago I developed a program to calculate the optimum betting amount for a round of Texas Hold 'em by using the Kelly criterion. In the process of computing the probability of winning for ...
4
votes
4answers
128 views

Find a generating function for the number of strings

The string $AAABBAAABB$ is a string of ten letters, each of which is $A$ or $B$, that does include the consecutive letters $ABBA$. Determine, with justification, the total number of strings of ten ...
0
votes
1answer
29 views

Coloring points on a circle

On a circle there are $n$, $n \ge 3$ points. In how many ways can we color them in $m$, $m \ge 2$, colors, so that neighbour points have different colors? We shouldn't use all $m$ colors. ...
13
votes
6answers
208 views

How to prove that $\sum_{i=0}^n 2^i\binom{2n-i}{n} = 4^n$.

So I've been struggling with this sum for some time and I just can't figure it out. I tried proving by induction that if the sum above is a $S_n$ then $S_{n+1} = 4S_n$, but I didn't really succeed so ...
1
vote
2answers
82 views

Scheduling gym class

My cousin came to me with this problem yesterday: She has 8 students in her gym class. In tomorrows class she has planned 4 different activities to rotate them through, each of which requires ...
2
votes
2answers
79 views

Number of polynomials which are divisible by $x+1$

Let $a,b,c,d$ be four integers (not necessarily distinct) in the set ${1,2,3,4,5}$ . The number of polynomials $f(x)=x^4+ax^3+bx^2+cx+d$ which are divisible by $x+1$ are: $(A)$ Between 55 and 65 ...
0
votes
2answers
37 views

What does this definition of permutation mean?

A simple question. They give the definition of permutation as "a one to one mapping of the set onto the set of positive integers $\{1, 2,3,4, \ldots n\}$." What does this definition exactly ...
1
vote
1answer
27 views

Permutations acting on coordinates of codewords

Let $\mathcal{C}$ be a binary code of length $n$. The automorphism group of $\mathcal{C}$ is defined to be the set of permutations in $S_n$ that take $\mathcal{C}$ to itself. The text by MacWilliams ...
1
vote
1answer
33 views

Permutation and Combination to find pairs

In how many different ways students can be paired such that no pair consists of 2 boys. Given :- Total students = 10, Girls = 7, boys = 3. What my approach is 3 boys can be paired with 7 girls like ...
2
votes
3answers
51 views

Intuitive explanation of $(1-x)^{-a-1}=\sum_{j=0}^{\infty}{{a+j} \choose j}x^j$

Could anyone please explain me the reasoning behind this formula? $(1-x)^{-a-1}=\sum_{j=0}^{\infty}{{a+j} \choose j}x^j$ Thanks so much!
0
votes
1answer
26 views

How to find the number of faces of a rhombicosadodecahedron?

I need to use the Euler's formula. I know there are $62$ faces...first, how do I find the number of vertices it has. From there, I can get the amount of edges, which will then in turn get me the ...
2
votes
0answers
42 views

Write as a product of integers [closed]

My question is that in how many ways can $10,000!$ be written as the product of $30$ distinct positive integers. My question is similar to this question: In how many ways can $1000000$ be expressed as ...
0
votes
1answer
42 views

Proving binomial identities [duplicate]

Can someone help me prove these two binomial identities using either walks in Pascal's triangle or a committee-selection model? $(1)$ $\qquad$ $\displaystyle\sum_{k=0}^m {m\choose k}{n\choose ...
0
votes
2answers
46 views

Finding expected number coin flips to get 2 consecutive heads [duplicate]

First, I know what the right answer is, and I know how to solve it. What I'm trying to figure out is why I can't get the following process to work. The probability that we get 2 consecutive heads ...
4
votes
2answers
39 views

Must the number of people…

Must the number of people at the party who do not know an odd number of people be even? Describe a graph model and then answers the question. I'm confused because I do not understand the ...
0
votes
5answers
63 views

How many ways to choose $ i,j,k,l$ from $1,\ldots, n$ such that $i<j$ and $k<l$

I am trying to work my way through the proof of Lemma 2 in Broder, A., & Karlin, A. R. (1990). Multilevel Adaptive Hashing. SODA 90 in order to generalise it as explained in a related question. I ...
0
votes
1answer
25 views

Is there an estimate for how much k-element subsets are needed to have any t-element subset in at least one of them?

Let's call $S(t, k, n)$ a minimal number of $k$-element subsets (blocks) of an $n$-element set $S$ with the property that each $t$-element subset of $S$ is contained in at least one block. Are there ...
1
vote
1answer
19 views

Finding a binary column vector that makes all rows distinct

Say I have a collection $\mathcal{M}$ of distinct binary matrices $M_i$, $i = 1, \dots, \binom{k+1}{k-1}$ of size $2^{k-1} \times (k-1)$ where in each $M_i$, all rows are distinct (note: $M_i$ is not ...
0
votes
2answers
54 views

Division n items into k boxes prove that it is NP-Complete

I don't know how to solve this problem. Can anyone help me with it please? I need to prove that this is a NP-complete problem. We are given $n$ items with sizes $s_1, s_2, ... ,s_n$, where $0 < ...
-1
votes
1answer
16 views

Self-avoiding walks from one diagonal to the other on $mxn$ lattice is ${m+n \choose m,n} $

According to wikipedia "self-avoiding walks from one end of a diagonal to the other, with only moves in the positive direction, there are exactly $$ \binom{n+m}{n,m} $$paths for an $m × n$ ...
0
votes
5answers
84 views

How many triplets $(x,y,z)$ can we make with $x,y,z\in\{1,\ldots,25\}$, where $x\leq y\leq z$? [closed]

The numbers $x$, $y$ and $z$ are chosen from the set of $\{1,2,3,\ldots,25\}$ such that $z\geq y\geq x$. In how many different ways can we from such triplets?
1
vote
0answers
47 views

How to use sub-pattern frequencies to calculate the authenticity the main pattern

I'm trying to determine the probability that something is real by comparing the frequency of the sub-permutations it contains. Here is an example: You want to guess whether or not a random symbol is ...
3
votes
3answers
63 views

Five people have applied for three different positions in a store. In how many ways can the positions be filled?

Five people have applied for three different positions in a store. If each person is qualified for each position, in how many ways can the positions be filled? Can someone tell me if I have to ...
1
vote
0answers
29 views

Smallest set of n-digit, base-m numerals containing every digit assignment to any 2 places?

I am interested in whether this is a familiar problem (I know it's a problem of familiar types, such as a set cover problem). To put the problem in the subject line another way, for a set $M$ with ...
0
votes
0answers
20 views

Monovariant problem

The problem is stated as follows: $200$ people are in a circle and have a real number assigned to them, such that the absolute difference of $2$ neighboring values is between $1$ and $3$ and the sum ...
0
votes
1answer
28 views

Three rounds, three bets: how to guarantee a loss of all three rounds

Suppose you are buying tickets for three round of some game. Your ticket must have three bets on it before the first round starts. Your three options for each round are for a win, a loss and a draw. ...
4
votes
2answers
55 views

Counting numbers of fruit baskets

Suppose you have $10$ apples, $12$ bananas, and $8$ peaches, and you want to divide them into $3$ baskets containing $10$ fruit each. In how many ways can you do this, if the fruit of each type is ...
0
votes
0answers
241 views

Number of ways to express a Fibonacci number as the sum of N other Fibonacci Numbers.

How do I find the number of ways to express a Fibonacci number as the sum of N other Fibonacci Numbers? There can be repetitions. Consecutive Fibs are allowed.
3
votes
2answers
48 views

Combinatorics - Number of Paths in a Grid with a Hole

Given a $12\times12$ grid with a hole of $4\times4$ in its middle, how many short paths (right or up only) are there from $(0,0)$ to $(12,12)$. I tried using inclusion-exclusion by counting the ...
0
votes
0answers
33 views

Calculate number of trials reaching $p_k$ probability for $k$ successes given the $p_t$ probability of each trial success

Basically, I'd like to be able to answer questions in the form of "What is the number of trials needed to have at least $p_k$ probability of at least $k$ successes, given that on each trial the ...
0
votes
0answers
34 views

Compute intersection size of a large number of sets

Consider a ground set $N:=\{1,\dotsc,n\}$. Let $X,Y \subseteq N$, $|X|=|Y|=s$, and disjoint. Let $X'\subseteq X$ with $|X'|= x$. Now suppose that for each $x' \in X'$ we have a set $Y_{x'} \subseteq ...
0
votes
0answers
79 views

Help me to solve $\overline{abc} \cdot d +\overline{ef}\cdot g + h \cdot i = 2010$

The problem is: $$(a \cdot 100 + b \cdot 10 + c ) \cdot d + (10\cdot e + f ) \cdot g + h \cdot i = 2010$$ and $$\{a, b, c, d, e, f, g, h, i\} = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}.$$(not allowed to repeat). ...
0
votes
0answers
22 views

Compute probability that a random subset has a certain property (when we know probability for an arbitrary subset)

Suppose we have a ground set $[n]:=\{1, \dotsc, n\}$. Now, we pick a random subset $S \subseteq [n]$ u.a.r. among all the subsets of $[n]$ having size equal to $s$. In general, if we know that for ...
2
votes
3answers
141 views

A combinatorial task I just can't solve

Suppose you have $7$ apples, $3$ banana, $5$ lemons. How many options to form $3$ equal in size baskets ($5$ fruits in each) are exist? At first I wrote: $\displaystyle \frac{15!}{7!3!5!} $ But its ...
0
votes
1answer
62 views

Choose 3 letters.

Find in how many ways an arrangement of $3$ letters can be made from the $26$ different letters of the alphabet if any letter may be used once, twice or thrice. How many of these arrangements will not ...
8
votes
5answers
457 views

counting probability with multiple cases

There are four different colors of paint one can use for four different houses. If one color can be used up to three times, how many total possibilities are there? I approached the problem by ...
5
votes
1answer
44 views

Why do I keep choosing the wrong probability rule?

I was wondering if someone could help clarify probability rules, although I think I understand them, whenever I have a straight forward and/or probability question, I seem to want to do a permutation ...
1
vote
1answer
46 views

Formula for the number of the last 1 in the binary vector

Given a binary vector $x=\{x_1, x_2, \ldots, x_n\}$; $x_k \in \{0,1\}$ $\forall k\in\overline{1,n}$. It is obvious that the number of $1$'s in the vector $x$ is equal to the sum of all its ...
5
votes
1answer
51 views

How many $5$ card poker hands contain at least $1$ red and $1$ black card?

How many $5$ card poker hands contain at least $1$ red and $1$ black card? I used inclusion-exclusion to calculate my answer. The number of total poker card hands are:$$52\choose 5$$I have $26$ red ...
0
votes
1answer
68 views

How many times is $n=(l+1)(m+1)$ generated while progressing through $l,m \in \{1,…\}$?

The sequence $n = (l+1)(m+1)$ for $l,m \in \{1,...\}$ yields exactly all non-prime (compound) numbers $n$. In general each non-prime number in this way is yielded $M(n)$ times. What is $M(n)$? I came ...
0
votes
2answers
39 views

How many words exist that have exactly $5$ distinct consonants and $2$ identical vowels?

I'm new to combinatorics, Although I understood most of the concepts this one baffles me. How many words exist that have exactly $5$ distinct consonants and $2$ identical vowels? The Answer is ...
0
votes
0answers
36 views

Is this a good way of generating unique permutations?

This is something that I thought of on my own, though I am sure that I am not the first to think of it. The easiest way to explain this is by using an example. Suppose we want to find the unique ...
3
votes
1answer
33 views

Possible numbers of elements in 15 7-sets with pairwise 1-intersection

There are $15$ sets, $X_1,\dots,X_{15}$, each one with exactly $7$ elements. We know that $\displaystyle \bigcap_{i=1}^{15} X_i= \varnothing$ and $|X_i\cap X_j|=1$ whenever $i\neq j$. Let ...
1
vote
1answer
39 views

Finding a generating function for $\{(n+2)C_{n+1}\}^\infty_{n=0}$

I'm trying to come up with a generating function for $\{(n+2)C_{n+1}\}^\infty_{n=0}$ where $C_n$ is the $n$th Catalan number. I know we can write $(n+2)C_{n+1} = 2(2n+1)C_n$. I also tried to follow ...