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)

3
votes
3answers
71 views

Seating arrangements with no 3 objects together.

Suppose that five $1$'s and six $0$'s need to be arranged in such a way that no three $0$'s are consecutive. How many different arrangements are possible? This is a variation on a problem where ...
0
votes
1answer
17 views

Partitions of an integer where each summand appears at most four times

Find the generating function for the number of partitions of an integer (greater than zero), where each summand appears at most four times. Is it the following?
-1
votes
0answers
30 views

Chances in combinatorics [on hold]

There are 124 apples, you and 9 more people are taking them. What are the chances for you to take the one that you wanted?
1
vote
1answer
168 views

Probability that committee chosen from 8 men and 7 women has more men

A board of trustees of a university consists of 8 men and 7 women. A committee of 3 must be selected at random and without replacement. The role of the committee is to select a new president for ...
0
votes
1answer
37 views

Which formula to use to solve following problem? The number of combinations without repetition or smth. else? [closed]

I don't know combinatorics at all. Could anyone point section of combinatorics or wiki article to solve problem below? Girl has five red, four blue and four green flowers. She wants to plant all ...
2
votes
2answers
54 views

Understanding a Generating Function

This is from generating functionology by Herbert S Wilf. Here a rule is given as let f $\longleftrightarrow$ {$a_n$}$^{\infty}_0$ is a ordinary power series generating function and let k be a ...
0
votes
2answers
28 views

Linear Recurrences

I was working on linear recurrence... But I am having trouble with it. $a_0 = 1; a_1 = 2; a_k = 4a_{k-1} - 2a_{k-2}$ I found $a_2$ which is $$4a_1 - 2 a_0=4\cdot2 - 2\cdot 1 = 6$$ I found $a_3$ ...
-1
votes
1answer
151 views

Integer linear combinations of coprime integers

Consider the finite set $S=\{s_1,s_2,\dots,s_n\}$ such that $GCF(s_1,s_2,\dots,s_n)=1$. Show that $\exists n$ such that $n$ cannot be written as $n=c_1s_1+c_2s_2+\dots+c_ns_n \forall c_i,s_i \in ...
0
votes
1answer
39 views

Probability of most frequent occurrences of suits/values when drawing 4 cards from 52

Draw 4 cards from a card deck with 52 cards (4 colours and 13 values for each colour) one after the other -- none is put back. Let's have two discrete random varaibles X and Y. X counts the maximum ...
2
votes
1answer
39 views

Exponential generating functions counting

How many $10$-digit numbers use only the digits $0, 1, 2$ with each digit appearing at least twice or not at all? I know I need the coefficient of $\frac{x^{10}}{10!}$ in: ...
0
votes
2answers
68 views

how many ways can you divide 24 people into groups of two? [closed]

just can't seem to figure this out. I need to aquire a function for this scenario. I have tried to look at smaller forms of the problem. My problem is I am struggling to get the # of possibilities. ...
0
votes
2answers
326 views

calculate all combination of indistinguishable objects

I am thinking a question of picking $k$ objects out of $n$($n>k$). But among the $n=4m$ objects, only $m$ distinguishable objects. For example, a deck of poker cards, total $n=52$ cards, but we ...
4
votes
2answers
242 views

How many ways can 10 people be split into groups of 2 and 3?

How many ways can 10 people be split into groups of 2 and 3? the answer says ${5 \choose 2}$... But isn't it the answer if the question were: "How many ways can 5 people be split into groups of 2 and ...
0
votes
1answer
27 views

Prove that using generating function:For any $n ,k\in N$, the number of partitions of $n$ into parts

For any $n,k\in N$, the number of partitions of $n$ into parts, each of which appears at most $k$ times, is equal to the number of partitions of $n$ into parts the sizes which are not divisible by ...
1
vote
2answers
35 views

Arrangements of sets of k positions in a n-competitors race

Let $E(n)$ be the set of all possible ending arrangements of a race of $n$ competitors. Obviously, because it's a race, each one of the $n$ competitors wants to win. Hence, the order of the ...
1
vote
1answer
22 views

Probability of full house

I'm trying to calcualte the probability of a full house in a standard 52-card deck. We choose out of the thirteen kinds $2$ of them so $\binom{13}{2}$. There are $4$ houses of each card in the deck ...
1
vote
0answers
66 views

Finding coefficient in formal power series

How to do this kind of questions: Determine the value of the following coefficient: $[x^{33}](x+x^3)(1+5x^6)^{-13}(1-8x^9)^{-37}$
2
votes
2answers
61 views

How to calculate the Summation??

Can we get the formula in terms of N and k for this summation series? $$ A=\sum_{t=0}^N\sum_{s=0}^t\sum_{r=0}^sk^rk^{s-r}k^{t-s} $$
0
votes
3answers
153 views

Proving prime number combinatorics

I am trying to figure out the following review problem: Let $p$ be a prime number and $a$ be a natural number. Prove that the following (parts 1, 2, 3 and 4) are true for every $p$ and $a$. Here, ...
1
vote
1answer
10 views

What is $R(k,l)$?

I'm reading Landman/Robertson's: Ramsey Theory on the Integers. It states the following theorem: Theorem 1.15 (Ramsey's Theorem for Two Colors). Let $k,l \geq 2$. There exists a least positive ...
1
vote
1answer
30 views

How to find a formula for these generating sequences?

It is given that $a_{0}=1$ , $b_{0}=0$ , $c_0=0$ $$ c_n= xc_{n-1}+x(x-1)a_{n-1}(3b_{n-1}+(x-2)a_{n-1}^{2})) $$ $$ b_n=xb_{n-1}+x(x-1)a_{n-1}^{2} $$ $$ a_n=xa_{n-1}+1 $$ where x is any constant. ...
0
votes
2answers
314 views

In how many ways can we arrange 40 boys and 20 girls in 5 groups of 12 members each, so that each group contains at least one girl.

My approach There are 5 groups with 12 members each,so if there was condition like there should be 3 girls and 2 boys i would do (20C3)*(40C2) But here it is given as atleast one girl,how to ...
0
votes
1answer
35 views

Ordering People

How many ways are there to order $3$ boys and $3$ girls when the girls sit together and same for the boys. How many ways are there to order $3$ boys and $3$ girls when $2$ boys can not sit ...
4
votes
2answers
54 views

Expected value of max of three numbers

This is a combo problem that a friend came up with some time ago, and recently showed to me. He claims he solved it when it first occurred to him, but can no longer remember the solution, and neither ...
1
vote
1answer
46 views

Binomial Theorem…extra indexed term.

I have the following expression: $$\sum_{i=0}^{n}\binom{n}{i}(2x+1)^{n-i}(-1)^ii!$$ Without the $i!$, the above expression would simply reduce to $(2x)^n$, but is there a way, or method for ...
0
votes
1answer
21 views

How to select four points so that origin is not contained in convex hull of these points?

I have a regular 12-gon $A_1A_2...A_{12}$ with centre $O$. How to select four points so that centre $O$ doesn't lie in and lie on quadrilateral? I tried. With diameter $A_{12}A_6$, consider ...
-1
votes
1answer
42 views
0
votes
1answer
33 views

How many ways can $3$ black counters and $5$ red counters be selected from a bag containing $7$ of each? [closed]

In how many ways can we choose 3 black counters and 5 red counters from a bag containing 7 black counters and 7 red counters?
4
votes
2answers
159 views

Is there a simple expression of this sum related to the coefficients of a generating function of $e^{x+x^2/2}$?

Suppose you have a formula $$ \sum_{n\geq 0}f(n)\frac{x^n}{n!}=\exp\left(x+\frac{x^2}{2}\right). $$ There is a recurrence for $f(n)$ found by differentiation, $$ \sum_{n\geq ...
2
votes
1answer
55 views

Arrange the 26 letters of the alphabet in a row such that certain words do not occurr

How many ways are there to arrange the 26 letters of the alphabet in a row such that none of the following words are formed by consecutive letters in the arrangement INCH, LOST, or THIN? The answer ...
4
votes
2answers
84 views

Matrices and Combinatorics are a bad combination.

Let $\scr A$ be the set of all $n\times n$ symmetric matrices all of whose entries are either $0$ or $1$ and such that if $n$ is even, $n^2/2$ of these entries are $1$ and $n^2/2$ of them are $0$, and ...
2
votes
0answers
60 views

Tricky combinatorics problem

I'm trying to solve the following problem: You get $15$ free spins on a slot machine, with a $0.01$ chance of re-triggering a further $15$ spins when a certain symbol falls on the centre reel. You ...
0
votes
2answers
30 views

Traveling salesman problem (TSP): what is the Relation with number of vertices and length of the found route?

I know that there are many algorithms (exact or approximate) which implement the traveling salesman problem. I would like to know the relation between the number of the vertices (i.e., the places to ...
-1
votes
0answers
15 views

Select k non overlapping rectangles in a $n \times m$ grid

We are given a given a $n \times m$ grid with $nm$ points. We have to select $k$ rectangles(obviously with corners lying at lattice points) such that no $2$ of them overlap. We can give a recurrence ...
1
vote
0answers
14 views

The maximum size of an antichain in a poset

Given $A$ as an n-element set and $X=p(A)$, I need to show that if $F$ is an antichain in the poset $(X,\subseteq)$ such that the maximum size of $F$'s elements is $n/2$ then $\mid F \mid \leq (_k^n)$ ...
1
vote
1answer
43 views

Distributing identical objects into distinct boxes

The problem I'm trying to solve is: find the number of ways of distributing $r$ identical objects into $n$ distinct boxes such that no box is empty, where $r \geq n$. I've found conflicting answers ...
1
vote
1answer
37 views

Splitting parties into committees

I feel like this should be an extremely simple problem, but I can't quite figure it out. How many ways are there to split $2n + 1$ places in a committee among $3$ nonempty parties, such that a ...
2
votes
3answers
30 views

Proving the combinatorial expression

Ok I've been reading in my probability book about the different methods on how to count and I'm just trying to dissect the usual combinatorial formula: $$\binom {a} {b} = \frac{a!}{b!(a-b)!}$$ ...
1
vote
2answers
39 views

How many five digit positive integer numbers are possible that each of the digits but the last one, is $\ge$ the next digit?

How many five digit positive integer numbers are possible that each of the digits but the last one, is $\ge$ the next digit? How do I approach this problem?
0
votes
1answer
113 views

If a coin is flipped 25 times with eight tails occurring, what is the probability that no run of $6$ or more heads occurs?

I'm trying to approach this question using generating functions. I set the problem up similar to a "toss $17$ balls into $9$ bins, what's the probability that no bin gets $6$ or balls in it." as the ...
0
votes
1answer
26 views

Counting binary strings of length n with no two adjacent 1's

I need to calculate the total number of possible binary strings of length $n$ with no two adjacent 1's. Eg. for n = 3 f(n) = 5 000,001,010,100,101 How do I solve ...
2
votes
2answers
36 views

Finding Number of Ordered Solutions to Equation

$$ A \times B \times C \times D \times E \times F = 7 \times 10^7 $$ How can I find the number of ordered solutions for integers (I mean for integers $A,B,C,D,E,F$) so that they can satisfy the ...
1
vote
1answer
29 views

Select $k$ non overlapping segments from $n$ points

We have $n$ points , say labeled from $1$ to $n$. We have to select $k$ segments from it so that no $2$ overlap. One possible solution would be by using a recurrence relation $f(k,n)=\sum ...
1
vote
0answers
65 views

The best strategy to increase StackExchange Reputation [closed]

I do not have a lot of background in game theory, but I am curious how would one formally pose the title problem and mathematically describe possible strategies. Are the problems of this type best ...
4
votes
4answers
71 views

Proof of an equation involving Stirling numbers of the second kind

I found this equation involving Stirling numbers of the second kind on Math World: $$\sum\limits_{m=1}^n (-1)^m(m-1)!\,S(n,m)=0 \ .$$ However, I do not know why this is true. I am looking for a proof ...
2
votes
2answers
106 views

A question about $ (2 \times 3) $-rectangles.

The following is a problem from TopCoder: Problem. Given the width and the height of a rectangular grid, return the total number of non-square rectangles that can be found on the grid. For ...
9
votes
5answers
871 views

A seemingly easy combinatorics brain teaser

So I have a brain teaser that goes like this: There's a school that awards students that, during a given period, are never late more than once and who don't ever happen to be absent for three ...
0
votes
0answers
31 views

How to asses the order of combinations

Let $\{a_i\}_{i=1}^m$ be some increasing sequence, bounded away from zero. How to see that as $n\to\infty$, we obtain $$\begin{pmatrix} n\\ m \end{pmatrix}^{-1}\sum_{i=1}^m\begin{pmatrix} ...
1
vote
0answers
57 views

Multinomial Theorem for Negative Exponents

Using an analog to Newton's binomial theorem with negative exponents, is it true that $$ \begin{align} \left(\sum_{k=0}^mx^k\right)^{-n} & = \sum_{0\le ...
0
votes
0answers
11 views

TREE-SEARCH finding key $k$

Prove that the TREE−SEARCH algorithm finds a key, if this belongs to a binary search tree to which the algorithm is applied. I am unsure how to answer this. In our notes it says: If $k$ is the key ...